package 数据结构专栏.A_二叉树专栏;


/**
 * @DESC 平衡二叉树即左右两棵子树高度差不大于1的二叉树。
 * <p>
 * 条件：
 * 它的左子树是平衡二叉树，
 * 它的右子树是平衡二叉树，
 * 它的左右子树的高度差不大于1。
 * <p>
 * 在我们眼里，这颗二叉树就3个节点：root、left、right
 *
 * https://lyl0724.github.io/2020/01/25/1/
 *
 *
 * @Author tzq
 * @Date 2020-04-01 10:02
 **/
public class _110_平衡二叉树 {
    public static void main(String[] args) {
        // 给定二叉树 [3,9,20,null,null,15,7]
        TreeNode root = new TreeNode(3);
        TreeNode t1 = new TreeNode(9);
        TreeNode t2 = new TreeNode(20);
        TreeNode t3 = new TreeNode(15);
        TreeNode t4 = new TreeNode(7);
        root.left = t1;
        root.right = t2;
        t2.left = t3;
        t2.right = t4;

        System.out.println(new _110_平衡二叉树().isBalanced(root)); // false ??


    }

    public boolean isBalanced(TreeNode root) {
        return isBST(root).isB;

    }

    private ReturnNode isBST(TreeNode root) {

        // 1. 递归终止条件 root == null
        if (root == null) {
            return new ReturnNode(true, 0);
        }

        // 2.不平衡的情况有3种：左树不平衡、右树不平衡、左树和右树差的绝对值大于1
        ReturnNode left = isBST(root.left);
        ReturnNode right = isBST(root.right);
        if (left.isB == false || right.isB == false) {
            return new ReturnNode(false, 0);
        }
        if (Math.abs(left.depth - right.depth) > 1) {
            return new ReturnNode(false, 0);
        }

        // 3. 剩下的就是平衡的，树的深度为左右俩子树最大深度+1
        return new ReturnNode(true, Math.max(left.depth, right.depth) + 1);
    }


}

/**
 * 返回的信息应该是既包含子树的深度的int类型的值，又包含子树是否是平衡二叉树的boolean类型的值
 */
class ReturnNode {
    boolean isB;
    int depth;

    //构造方法
    public ReturnNode(boolean isB, int depth) {
        this.isB = isB;
        this.depth = depth;
    }
}


/**
 * 递归解决，计算子树高度，-1表示子树已经不平衡了
 */
class Solution2 {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }
    private int height(TreeNode root) {
        if (root == null)
            return 0;
        int lh = height(root.left), rh = height(root.right);
        if (lh >= 0 && rh >= 0 && Math.abs(lh - rh) <= 1) {
            return Math.max(lh, rh) + 1;
        } else {
            return -1;
        }
    }
}